def fibonacci_memo(n: int) -> int:
    """斐波那契数列
    获取斐波那契数列的第n项的值。
    Args:
        n (int): 自然数n；

    Returns:
        int: 值。
    """
    memorandum: list[int] = [0, 1] + [0] * (n - 1) if n > 1 else []

    def dp(n: int):
        """
        docstring
        """
        if n == 0 or n == 1:
            return memorandum[n]
        else:
            if memorandum[n] == 0:
                memorandum[n] = dp(n - 1) + dp(n - 2)
            return memorandum[n]

    return dp(n)


def fibonacci_table(n: int) -> int:
    """
    斐波那契数列表格法。
    """

    dp: list[int] = [0, 1] + [0] * (n - 1) if n > 1 else []

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


def fibonacci_constract(n: int) -> int:
    """
    斐波那契数列
    """
    a: int = 0
    b: int = 1

    for i in range(n):
        a, b = b, a + b

    return a


if __name__ == "__main__":
    print(fibonacci_table(40))
